{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Total Distance Traveled"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTotalDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小移动总距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>X 轴上有一些机器人和工厂。给你一个整数数组&nbsp;<code>robot</code>&nbsp;，其中&nbsp;<code>robot[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个机器人的位置。再给你一个二维整数数组&nbsp;<code>factory</code>&nbsp;，其中&nbsp;<code>factory[j] = [position<sub>j</sub>, limit<sub>j</sub>]</code>&nbsp;，表示第 <code>j</code>&nbsp;个工厂的位置在&nbsp;<code>position<sub>j</sub></code>&nbsp;，且第 <code>j</code>&nbsp;个工厂最多可以修理&nbsp;<code>limit<sub>j</sub></code>&nbsp;个机器人。</p>\n",
    "\n",
    "<p>每个机器人所在的位置 <strong>互不相同</strong>&nbsp;。每个工厂所在的位置也 <strong>互不相同</strong>&nbsp;。注意一个机器人可能一开始跟一个工厂在 <strong>相同的位置</strong>&nbsp;。</p>\n",
    "\n",
    "<p>所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。</p>\n",
    "\n",
    "<p><b>任何时刻</b>，你都可以设置&nbsp;<strong>部分</strong>&nbsp;机器人的移动方向。你的目标是最小化所有机器人总的移动距离。</p>\n",
    "\n",
    "<p>请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>所有机器人移动速度相同。</li>\n",
    "\t<li>如果两个机器人移动方向相同，它们永远不会碰撞。</li>\n",
    "\t<li>如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。</li>\n",
    "\t<li>如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。</li>\n",
    "\t<li>机器人从位置&nbsp;<code>x</code> 到位置&nbsp;<code>y</code>&nbsp;的移动距离为&nbsp;<code>|y - x|</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1667542978-utuiPv-image.png\" style=\"width: 500px; height: 320px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>robot = [0,4,6], factory = [[2,2],[6,2]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>如上图所示：\n",
    "- 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。\n",
    "- 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。\n",
    "- 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。\n",
    "第一个工厂的维修上限是 2 ，它维修了 2 个机器人。\n",
    "第二个工厂的维修上限是 2 ，它维修了 1 个机器人。\n",
    "总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1667542984-OAIRFN-image.png\" style=\"width: 500px; height: 329px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>robot = [1,-1], factory = [[-2,1],[2,1]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>如上图所示：\n",
    "- 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。\n",
    "- 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。\n",
    "第一个工厂的维修上限是 1 ，它维修了 1 个机器人。\n",
    "第二个工厂的维修上限是 1 ，它维修了 1 个机器人。\n",
    "总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= robot.length, factory.length &lt;= 100</code></li>\n",
    "\t<li><code>factory[j].length == 2</code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= robot[i], position<sub>j</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= limit<sub>j</sub> &lt;= robot.length</code></li>\n",
    "\t<li>测试数据保证所有机器人都可以被维修。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-total-distance-traveled](https://leetcode.cn/problems/minimum-total-distance-traveled/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-total-distance-traveled](https://leetcode.cn/problems/minimum-total-distance-traveled/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,4,6]\\n[[2,2],[6,2]]', '[1,-1]\\n[[-2,1],[2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        # 1. 递归： 邻项交换：对机器人和工厂按照位置大小重新排序，每个工厂修复的机器人就是连续的一段\n",
    "        # factory.sort(key = lambda f: f[0])\n",
    "        # robot.sort()\n",
    "        # n, m = len(factory), len(robot)\n",
    "\n",
    "        # @cache\n",
    "        # def f(i:int, j:int)-> int: # f(i,j) 表示用第i个及其右侧的工厂，修理第j个及其右侧的机器人，移动的最小总距离\n",
    "        #     if j == m: return 0\n",
    "        #     if i == n - 1:\n",
    "        #         if m - j > factory[i][1]: return inf\n",
    "        #         return sum(abs(x - factory[i][0])for x in robot[j:])\n",
    "        #     res = f(i + 1, j)\n",
    "        #     s, k = 0, 1\n",
    "        #     while k <= factory[i][1] and j + k - 1 < m:\n",
    "        #         s += abs(robot[j + k - 1] - factory[i][0])\n",
    "        #         res = min(res, s + f(i + 1, j + k)) # \n",
    "        #         k += 1\n",
    "        #     return res\n",
    "        # return f(0, 0)\n",
    "    \n",
    "        # 2. 递推\n",
    "        factory.sort(key = lambda f: f[0])\n",
    "        robot.sort()\n",
    "        m = len(robot)\n",
    "        f = [0] + [inf] * m\n",
    "        for pos, limit in factory:\n",
    "            for j in range(m, 0, -1):\n",
    "                cost = 0\n",
    "                for k in range(1, min(j, limit) + 1):\n",
    "                    cost += abs(robot[j - k] - pos)\n",
    "                    f[j] = min(f[j], f[j - k] + cost)\n",
    "        return f[m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        factory.sort(key=lambda f: f[0])\n",
    "        robot.sort()\n",
    "        m = len(robot)\n",
    "        f = [0] + [inf] * m\n",
    "        for pos, limit in factory:\n",
    "            for j in range(m, 0, -1):\n",
    "                cost = 0\n",
    "                for k in range(1, min(j, limit) + 1):\n",
    "                    cost += abs(robot[j - k] - pos)\n",
    "                    f[j] = min(f[j], f[j - k] + cost)\n",
    "        return f[m]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\r\n",
    "        factory.sort(key=lambda f: f[0])\r\n",
    "        robot.sort()\r\n",
    "        m = len(robot)\r\n",
    "        f = [0] + [inf] * m\r\n",
    "        for pos, limit in factory:\r\n",
    "            for j in range(m, 0, -1):\r\n",
    "                cost = 0\r\n",
    "                for k in range(1, min(j, limit) + 1):\r\n",
    "                    cost += abs(robot[j - k] - pos)\r\n",
    "                    f[j] = min(f[j], f[j - k] + cost)\r\n",
    "        return f[m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        nR, nF = len(robot), len(factory)\n",
    "        inf = float('inf')\n",
    "        states = [inf]*(nR+1)\n",
    "        states[0] = 0\n",
    "        res = inf\n",
    "        for fPos, fLimit in factory:\n",
    "            for iR in range(nR, 0, -1):\n",
    "                _sum = 0\n",
    "                for d in range(1, min(iR, fLimit)+1):\n",
    "                    _sum += abs(fPos - robot[iR-d])\n",
    "                    states[iR] = min(states[iR], states[iR-d] + _sum)\n",
    "                # states[iR] = min((states[iR-d] if iR>=d else inf) + sum(abs(fPos - robot[off-1]) for off in range(max(iR-d+1, 1), iR+1)) for d in range(fLimit+1))\n",
    "            res = min(res, states[-1])\n",
    "        return res\n",
    "        \n",
    "\n",
    "        # R[f][r] = min(R[f-1][r-k] +  sum(dist[f][r...r-k+1]))\n",
    "        # R[0][0] = 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        dp = [[inf] * (m + 1) for _ in range(n + 1)]\n",
    "        \n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = 0\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            pos, limit = factory[i - 1]\n",
    "            for j in range(1, m + 1):\n",
    "                cost = 0\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                for k in range(1, min(limit, j) + 1):\n",
    "                    cost += abs(pos - robot[j - k])\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][j - k] + cost)\n",
    "        # print(dp)\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        dp = [[inf] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            pos, limit = factory[i - 1]\n",
    "            for j in range(m + 1):\n",
    "                cost = 0\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                for k in range(1, min(limit, j) + 1):\n",
    "                    cost += abs(pos - robot[j - k])\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][j - k] + cost)\n",
    "        # print(dp)\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m = len(robot)\n",
    "        n = len(factory)\n",
    "\n",
    "        # f[i][j] 表示前i个工厂修理 前j个机器人的总移动距离最小。\n",
    "        f = [[inf] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            f[i][0] = 0 \n",
    "        for i in range(1, n + 1):\n",
    "            pos, limit = factory[i - 1]\n",
    "            for j in range(1, m + 1):\n",
    "                f[i][j] = min(f[i][j], f[i - 1][j])\n",
    "                cost = 0\n",
    "                for k in range(1, min(limit, j) + 1):\n",
    "                    cost += abs(robot[j - k] - pos)\n",
    "                    f[i][j] = min(f[i][j], f[i - 1][j - k] + cost)\n",
    "        # print(f)\n",
    "        return f[n][m]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m = len(robot)\n",
    "        n = len(factory)\n",
    "        # f[i][j] 前i个工厂修理前j个机器人的最小花费\n",
    "        f = [[inf] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            f[i][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            pos, limit = factory[i - 1]\n",
    "            for j in range(1, m + 1):\n",
    "                cost = 0\n",
    "                f[i][j] = f[i - 1][j]\n",
    "                # 第i个工厂修理机器人k~j\n",
    "                for k in range(1, min(j, limit) + 1):\n",
    "                    cost += abs(robot[j - k] - pos)\n",
    "                    f[i][j] = min(f[i][j], f[i - 1][j - k] + cost)\n",
    "        return f[n][m]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        robot.sort()\n",
    "        for i in range(len(factory)):\n",
    "            for j in range(len(robot)):\n",
    "                distance = abs(factory[i][0] -robot[j])\n",
    "        \"\"\"\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        n, m = len(robot), len(factory)\n",
    "\n",
    "        # dp[i][j] 表示截至下标 i 的 factory，装下 j 个 robot ，总的 cost 最小能达到多少\n",
    "        dp = [[math.inf] * (n + 1) for _ in range(m)]\n",
    "        # 所有dp[i][0]=0因为截至下标i一个robot都不修显然没有开销\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 0\n",
    "        # 初始化，考虑第一个factory，能装几个装几个，我们看截至下标0在尽量装robot的情况下总开销是多少\n",
    "        for j in range(1, min(factory[0][1], n) + 1):\n",
    "            dp[0][j] = dp[0][j - 1] + abs(factory[0][0] - robot[j - 1])\n",
    "\n",
    "        # 这里遍历的i是从0到m-2，是因为采取了从前向后递推的形式，\n",
    "        # 而没有用dp[i][j] = dp[i-1][j-k] + cost(last k robots to factory[i])这种向前找的形式\n",
    "        for i in range(0, m - 1):\n",
    "            for j in range(n):\n",
    "                # 如果当前dp[i][j] == math.inf，说明截至下标i根本无法装下j个robot，\n",
    "                # 那么这是个不合法状态，且同一个i下后续的j显然也不合法，直接break掉即可\n",
    "                if dp[i][j] == math.inf:\n",
    "                    break\n",
    "                # 用dp[i][j]更新一下dp[i + 1][j]，因为存在这种可能，\n",
    "                # j个robot都在截至下标i及之前的factory修更好，而不是分配一些到下标第i+1个\n",
    "                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])\n",
    "                # temp用来记录将接下来k个robot调往factory[i + 1]维修的总开销\n",
    "                temp = 0\n",
    "                # 看factory[i + 1]能装下多少，有一个算一个都往里面装\n",
    "                for k in range(1, factory[i + 1][1] + 1):\n",
    "                    # 总共只有n个robot，j + k > n 显然不可能。\n",
    "                    if j + k > n:\n",
    "                        break\n",
    "                    temp += abs(robot[j + k - 1] - factory[i + 1][0])\n",
    "                    dp[i + 1][j + k] = min(dp[i + 1][j + k], dp[i][j] + temp)\n",
    "\n",
    "        # 找所有装下了n个robot的状态中的最小值\n",
    "        return int(min(dp[i][-1] for i in range(m)))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        n = len(robot)\n",
    "        m = len(factory)\n",
    "        robot.sort()\n",
    "        factory.sort(key = lambda x: x[0])\n",
    "        s = 0\n",
    "        pre = []\n",
    "        for pos, limit in factory:\n",
    "            pre.append(s)\n",
    "            s += limit\n",
    "        pre.append(s)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[0][i] = 200000000000\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if j > pre[i]:\n",
    "                    dp[i][j] = 200000000000\n",
    "                    continue\n",
    "                # minn = max(0, j - pre[i-1])\n",
    "                maxn = min(j, factory[i-1][1])\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                pathlen = 0\n",
    "                for k in range(maxn):\n",
    "                    pathlen += abs(robot[j-1-k] - factory[i-1][0])\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][j-k-1] + pathlen)\n",
    "        # print(dp)\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        \n",
    "        sum_dis = [[0 for i in range(n)] for j in range(m)]\n",
    "        for j in range(n):\n",
    "            cumulative_sum = 0\n",
    "            for i in range(m):\n",
    "                cumulative_sum += abs(factory[j][0] - robot[i])\n",
    "                sum_dis[i][j] = cumulative_sum\n",
    "\n",
    "        dis = [[int(1e12) for i in range(n)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(factory[j][1] + 1):\n",
    "                    if i - k >= 0:\n",
    "                        prev_dis = dis[i - k][j - 1] if j > 0 else int(1e12)\n",
    "                        dis[i][j] =  min(dis[i][j],prev_dis + sum_dis[i][j] - sum_dis[i - k][j])\n",
    "                    else:\n",
    "                        dis[i][j] = min(dis[i][j], sum_dis[i][j])\n",
    "                        break\n",
    "        return dis[m - 1][n - 1]\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        dis = [[int(1e12) for i in range(n)] for j in range(m)]\n",
    "        # dis[i][j] 表示前 i + 1 个机器人, 前 j + 1 个工厂, 所能够达到的最小距离\n",
    "        sum_dis = [[0 for i in range(n)] for j in range(m)]\n",
    "        # 遍历 factory 中的每个元素\n",
    "        for j in range(n):\n",
    "            # 初始化累积和为零\n",
    "            cumulative_sum = 0\n",
    "            # 遍历 robot 数组，计算累积和\n",
    "            for i in range(m):\n",
    "                cumulative_sum += abs(factory[j][0] - robot[i])\n",
    "                sum_dis[i][j] = cumulative_sum\n",
    "        # sum_dis[i][j] = sum_{0 <= t <= i} abs(f[j][0] - robot[t])\n",
    "        # 先考虑最初始情况\n",
    "        # dis[0][0] = abs(robot[0] - factory[0])\n",
    "        # dis[i][j] = \n",
    "        # 考虑第 j 个工厂, 它到底能覆盖哪些呢? 这取决于它的 factory[j][1] \n",
    "        # dis[i][j] = dis[i - k][j - 1] + sum_{i - k < t <= i}abs(factory[j][0] - robot[t])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(factory[j][1] + 1):\n",
    "                    if k == 0: # 第 j 个不起作用\n",
    "                        if j == 0:\n",
    "                            dis[i][j] = int(1e12)\n",
    "                        else:\n",
    "                            dis[i][j] = dis[i][j - 1]\n",
    "                        continue\n",
    "                    # 第 j 个起了作用, 覆盖了 k 个\n",
    "                    # 剩余 j - 1 个覆盖了 0, ..., i - k 个\n",
    "\n",
    "                    if i - k >= 0:\n",
    "                        if j > 0:\n",
    "                            dis[i][j] = min(dis[i][j], dis[i - k][j - 1] + sum_dis[i][j] - sum_dis[i - k][j])\n",
    "                        else:\n",
    "                            dis[i][j] = int(1e12)\n",
    "                    else:\n",
    "                        dis[i][j] = min(dis[i][j], sum_dis[i][j])\n",
    "                        break\n",
    "            #     print(dis[i][j], end=', ')\n",
    "            # print()\n",
    "        return dis[m - 1][n - 1]\n",
    "        '''\n",
    "        - 首先注意到: 最优解不可能出现交叉的路径\n",
    "        - 最优解的形式应该是最左侧和最右侧的 r 先去往最近的 f, 剩下来的 r 必然在 [f_s, f_e] 的区间内\n",
    "        - 并且由于题给条件限制, 这个大区间的包含足够多的工厂维修额\n",
    "        - 最优解一定由一系列的区间构成, 区间端点为工厂, 并且区间内部没有交叉 (即左边若干个机器人向左, \n",
    "          右边若干个机器人向右)\n",
    "        - 接下来考虑大区间最左侧的那个 f_s\n",
    "        - f_s 右边第一个 r, 事实上, 它可以向左, 也可以向右\n",
    "        - 如果它向左, 就继续;\n",
    "        - 如果它向右, 那么需要确定一个右端点来分割区间\n",
    "\n",
    "        - Hint: 每个 f 实际上负责了一个子区间内的所有 r\n",
    "        - 因此, 如果使用动态规划, 状态该怎么变化? \n",
    "        - {r_0, ... ,r_i} 由 {f_0, ..., f_j} 负责, 产生的最小路径记为 g[i][j]\n",
    "        - 怎么状态转移?\n",
    "        - g[i][j] = \n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        \n",
    "        sum_dis = [[0 for i in range(n)] for j in range(m)]\n",
    "        for j in range(n):\n",
    "            cumulative_sum = 0\n",
    "            for i in range(m):\n",
    "                cumulative_sum += abs(factory[j][0] - robot[i])\n",
    "                sum_dis[i][j] = cumulative_sum\n",
    "\n",
    "        dis = [[int(1e12) for i in range(n)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                \n",
    "                for k in range(factory[j][1] + 1):\n",
    "                    # if k == 0: # 第 j 个不起作用\n",
    "                    #     if j == 0:\n",
    "                    #         dis[i][j] = int(1e12)\n",
    "                    #     else:\n",
    "                    #         dis[i][j] = dis[i][j - 1]\n",
    "                    #     continue\n",
    "                    # # 第 j 个起了作用, 覆盖了 k 个\n",
    "                    # # 剩余 j - 1 个覆盖了 0, ..., i - k 个\n",
    "\n",
    "                    if i - k >= 0:\n",
    "                        if j > 0:\n",
    "                            dis[i][j] = min(dis[i][j], dis[i - k][j - 1] + sum_dis[i][j] - sum_dis[i - k][j])\n",
    "                        else:\n",
    "                            dis[i][j] = int(1e12)\n",
    "                    else:\n",
    "                        dis[i][j] = min(dis[i][j], sum_dis[i][j])\n",
    "                        break\n",
    "            #     print(dis[i][j], end=', ')\n",
    "            # print()\n",
    "        return dis[m - 1][n - 1]\n",
    "        '''\n",
    "        - 首先注意到: 最优解不可能出现交叉的路径\n",
    "        - 最优解的形式应该是最左侧和最右侧的 r 先去往最近的 f, 剩下来的 r 必然在 [f_s, f_e] 的区间内\n",
    "        - 并且由于题给条件限制, 这个大区间的包含足够多的工厂维修额\n",
    "        - 最优解一定由一系列的区间构成, 区间端点为工厂, 并且区间内部没有交叉 (即左边若干个机器人向左, \n",
    "          右边若干个机器人向右)\n",
    "        - 接下来考虑大区间最左侧的那个 f_s\n",
    "        - f_s 右边第一个 r, 事实上, 它可以向左, 也可以向右\n",
    "        - 如果它向左, 就继续;\n",
    "        - 如果它向右, 那么需要确定一个右端点来分割区间\n",
    "\n",
    "        - Hint: 每个 f 实际上负责了一个子区间内的所有 r\n",
    "        - 因此, 如果使用动态规划, 状态该怎么变化? \n",
    "        - {r_0, ... ,r_i} 由 {f_0, ..., f_j} 负责, 产生的最小路径记为 g[i][j]\n",
    "        - 怎么状态转移?\n",
    "        - g[i][j] = \n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory = sorted([y[0] for y in factory for _ in range(y[1])])\n",
    "        # print(factory)\n",
    "        # m,n = len(robot),sum([x[1] for x in factory])\n",
    "        m, n = len(robot), len(factory)\n",
    "\n",
    "        # res = 0\n",
    "        # dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        for i in range( m ):\n",
    "            newdp = [0]*(n+1)\n",
    "            for j in range(i, n):\n",
    "                newdp[j + 1] = dp[j] + abs(robot[i] - factory[j])\n",
    "                if j>i:\n",
    "                    newdp[j+1] = min(newdp[j+1],newdp[j]+abs(robot[i]-factory[j])-abs(robot[i]-factory[j-1]))\n",
    "            dp = newdp\n",
    "        # pprint(dp[-1][m+1:])\n",
    "        return min(dp[m:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        # factory = sorted([y[0] for y in factory for _ in range(y[1])])\n",
    "        # print(factory)\n",
    "        # m,n = len(robot),sum([x[1] for x in factory])\n",
    "        m, n = len(robot), sum([x[1] for x in factory])\n",
    "\n",
    "        # res = 0\n",
    "        # dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        @cache\n",
    "        def getVal(i):\n",
    "            cur = 0\n",
    "            for x in factory:\n",
    "                cur += x[1]\n",
    "                if cur > i:\n",
    "                    return x[0]\n",
    "            return -1\n",
    "\n",
    "        for i in range( m ):\n",
    "            newdp = [0]*(n+1)\n",
    "            for j in range(i, n):\n",
    "                newdp[j + 1] = dp[j] + abs(robot[i] - getVal(j))\n",
    "                if j>i:\n",
    "                    newdp[j+1] = min(newdp[j+1],newdp[j]+abs(robot[i]-getVal(j))-abs(robot[i]-getVal(j-1)))\n",
    "            dp = newdp\n",
    "        # pprint(dp[-1][m+1:])\n",
    "        return min(dp[m:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        # factory = sorted([y[0] for y in factory for _ in range(y[1])])\n",
    "        # print(factory)\n",
    "        # m,n = len(robot),sum([x[1] for x in factory])\n",
    "        m, n = len(robot), sum([x[1] for x in factory])\n",
    "\n",
    "        # res = 0\n",
    "        # dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        @cache\n",
    "        def getVal(i):\n",
    "            cur = 0\n",
    "            for x in factory:\n",
    "                cur += x[1]\n",
    "                if cur > i:\n",
    "                    return x[0]\n",
    "            return -1\n",
    "\n",
    "        for i in range( m ):\n",
    "            newdp = [0]*(n+1)\n",
    "            for j in range(i, n):\n",
    "                newdp[j + 1] = dp[j] + abs(robot[i] - getVal(j))\n",
    "                if j>i:\n",
    "                    newdp[j+1] = min(newdp[j+1],newdp[j]+abs(robot[i]-getVal(j))-abs(robot[i]-getVal(j-1)))\n",
    "            dp = newdp\n",
    "        # pprint(dp[-1][m+1:])\n",
    "        return min(dp[m:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from typing import List, Tuple\n",
    "from collections import deque\n",
    "INF = int(1e18)\n",
    "class Edge:\n",
    "    __slots__ = (\"fromV\", \"toV\", \"cap\", \"cost\", \"flow\")\n",
    "    def __init__(self, fromV: int, toV: int, cap: int, cost: int, flow: int) -> None:\n",
    "        self.fromV = fromV\n",
    "        self.toV = toV\n",
    "        self.cap = cap\n",
    "        self.cost = cost\n",
    "        self.flow = flow\n",
    "class MinCostMaxFlowEK:\n",
    "    \"\"\"最小费用流的复杂度为流量*spfa的复杂度\"\"\"\n",
    "    __slots__ = (\"_n\", \"_start\", \"_end\", \"_edges\", \"_reGraph\", \"_dist\", \"_pre\", \"_flow\")\n",
    "    def __init__(self, n: int, start: int, end: int):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            n (int): 包含虚拟点在内的总点数\n",
    "            start (int): (虚拟)源点\n",
    "            end (int): (虚拟)汇点\n",
    "        \"\"\"\n",
    "        assert 0 <= start < n and 0 <= end < n\n",
    "        self._n = n\n",
    "        self._start = start\n",
    "        self._end = end\n",
    "        self._edges: List[\"Edge\"] = []\n",
    "        self._reGraph: List[List[int]] = [[] for _ in range(n)]  # 残量图存储的是边的下标\n",
    "\n",
    "        self._dist = [INF] * n\n",
    "        self._flow = [0] * n\n",
    "        self._pre = [-1] * n\n",
    "    def addEdge(self, fromV: int, toV: int, cap: int, cost: int) -> None:\n",
    "        \"\"\"原边索引为i 反向边索引为i^1\"\"\"\n",
    "        self._edges.append(Edge(fromV, toV, cap, cost, 0))\n",
    "        self._edges.append(Edge(toV, fromV, 0, -cost, 0))\n",
    "        len_ = len(self._edges)\n",
    "        self._reGraph[fromV].append(len_ - 2)\n",
    "        self._reGraph[toV].append(len_ - 1)\n",
    "    def work(self) -> Tuple[int, int]:\n",
    "        \"\"\"\n",
    "        Returns:\n",
    "            Tuple[int, int]: [最大流,最小费用]\n",
    "        \"\"\"\n",
    "        maxFlow, minCost = 0, 0\n",
    "        while self._spfa():\n",
    "            delta = self._flow[self._end]\n",
    "            minCost += delta * self._dist[self._end]\n",
    "            maxFlow += delta\n",
    "            cur = self._end\n",
    "            while cur != self._start:\n",
    "                edgeIndex = self._pre[cur]\n",
    "                self._edges[edgeIndex].flow += delta\n",
    "                self._edges[edgeIndex ^ 1].flow -= delta\n",
    "                cur = self._edges[edgeIndex].fromV\n",
    "        return maxFlow, minCost\n",
    "    def _spfa(self) -> bool:\n",
    "        \"\"\"spfa沿着最短路寻找增广路径  有负cost的边不能用dijkstra\"\"\"\n",
    "        n, start, end, edges, reGraph = (\n",
    "            self._n,\n",
    "            self._start,\n",
    "            self._end,\n",
    "            self._edges,\n",
    "            self._reGraph,\n",
    "        )\n",
    "        self._flow = flow = [0] * n\n",
    "        self._pre = pre = [-1] * n\n",
    "        self._dist = dist = [INF] * n\n",
    "        dist[start] = 0\n",
    "        flow[start] = INF\n",
    "        inQueue = [False] * n\n",
    "        inQueue[start] = True\n",
    "        queue = deque([start])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            inQueue[cur] = False\n",
    "            for edgeIndex in reGraph[cur]:\n",
    "                edge = edges[edgeIndex]\n",
    "                cost, remain, next = edge.cost, edge.cap - edge.flow, edge.toV\n",
    "                if remain > 0 and dist[cur] + cost < dist[next]:\n",
    "                    dist[next] = dist[cur] + cost\n",
    "                    pre[next] = edgeIndex\n",
    "                    flow[next] = remain if remain < flow[cur] else flow[cur]\n",
    "                    if not inQueue[next]:\n",
    "                        inQueue[next] = True\n",
    "                        if queue and dist[queue[0]] > dist[next]:\n",
    "                            queue.appendleft(next)\n",
    "                        else:\n",
    "                            queue.append(next)\n",
    "        return pre[end] != -1\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        n=len(robot)\n",
    "        m=len(factory)\n",
    "        st=n+m+5\n",
    "        ed=st+1\n",
    "        mc=MinCostMaxFlowEK(n+m+10,st,ed)\n",
    "        for i in range(n):\n",
    "            mc.addEdge(st,i,1,0)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                mc.addEdge(i,j+n,1,abs(robot[i]-factory[j][0]))\n",
    "        for j in range(m):\n",
    "            mc.addEdge(j+n,ed,factory[j][1],0)\n",
    "        return mc.work()[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        # 通过临项交换法可以证明，一个工厂必定修理一段排序后连续的机器人是最优的，即使每个工厂有修理上限\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        @cache\n",
    "        def dfs(i, j): # robot索引 [0..i] 内全部机器人被 factory 索引 [0..j]内的工厂修\n",
    "            if j == 0: # 最后一个工厂要修全部剩余的机器人\n",
    "                if i+1 > factory[0][1]: # 超过最后一个工厂的limit\n",
    "                    return inf\n",
    "                return sum(abs(factory[0][0]-pos) for pos in robot[:i+1])\n",
    "            if i == -1: \n",
    "                return 0\n",
    "            res = dfs(i, j-1) # 第j个工厂不修机器人\n",
    "            pre_sum = 0\n",
    "            for k in range(1, min(i+1, factory[j][1]) + 1): # 枚举第j个工厂修的机器人数量\n",
    "                pre_sum += abs(factory[j][0] - robot[i-k+1]) # [0..i] = [0..i-k] + [i-k+1..i]\n",
    "                res = min(res, dfs(i-k, j-1) + pre_sum)\n",
    "            return res\n",
    "        return dfs(m-1, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], fac: List[List[int]]) -> int:\n",
    "        n=len(robot)\n",
    "        robot.sort()\n",
    "        fac.sort()\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i<0:return 0\n",
    "            \n",
    "            if j==0:\n",
    "                if i+1>fac[0][1]:return inf\n",
    "                return sum(abs(fac[0][0]-robot[k]) for k in range(i+1))\n",
    "            ans=dfs(i,j-1)\n",
    "            pre=0\n",
    "            for count in range(1,fac[j][1]+1):\n",
    "                if count>i+1:break\n",
    "                    \n",
    "                ans=min(ans,dfs(i-count,j-1)+pre+(abs(fac[j][0]-robot[i-count+1]) if count else 0))\n",
    "                pre+=(abs(fac[j][0]-robot[i-count+1]) if count else 0)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(len(robot)-1,len(fac)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        factory.sort()\n",
    "\n",
    "        robot.sort()\n",
    "\n",
    "        m,n=len(robot),len(factory)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):   \n",
    "            if j<0:return 0\n",
    "            if i==0:\n",
    "                if j+1>factory[0][1]:return inf\n",
    "                return sum(abs(x-factory[0][0]) for x in robot[:j+1])\n",
    "\n",
    "            ans=dfs(i-1,j)\n",
    "            temp=0\n",
    "            for count in range(factory[i][1]):\n",
    "                if j-count<0:break\n",
    "                temp+=abs(robot[j-count]-factory[i][0])\n",
    "                ans=min(ans,temp+dfs(i-1,j-count-1))\n",
    "\n",
    "            return ans\n",
    "\n",
    "\n",
    "        return dfs(n-1,m-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort(key = lambda x:x[0])\n",
    "        n,m = len(factory),len(robot)\n",
    "\n",
    "        @cache\n",
    "        def f(i:int,j:int)->int:\n",
    "            if j ==-1 :\n",
    "                return 0\n",
    "             \n",
    "            if i == 0:\n",
    "                if j+1 > factory[i][1]:\n",
    "                    return inf\n",
    "                \n",
    "                return sum(abs(x -factory[i][0]) for x in robot[:j+1])\n",
    "            res = f(i-1,j)## 修0个\n",
    "\n",
    "            s ,k = 0, 1\n",
    "\n",
    "            while k <= factory[i][1] and j-k+1>=0:\n",
    "                s += abs(robot[j-k+1]-factory[i][0])\n",
    "                res = min(res,s+f(i-1,j-k))\n",
    "                k+=1\n",
    "            return res\n",
    "\n",
    "\n",
    "        return f(n-1,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        n, m = len(factory), len(robot)\n",
    "        factory.sort(key=lambda f:f[0])\n",
    "        robot.sort()\n",
    "\n",
    "        @cache \n",
    "        def f(i, j):\n",
    "            if j == m:\n",
    "                return 0\n",
    "            if i == n - 1:\n",
    "                if factory[i][1] < m - j:\n",
    "                    return inf \n",
    "                return sum(abs(factory[i][0] - x) for x in robot[j:]) \n",
    "            res = f(i + 1, j)\n",
    "            s, k = 0, 1\n",
    "\n",
    "            while k <= factory[i][1] and j + k - 1 < m:\n",
    "                s += abs(factory[i][0] - robot[j + k - 1])\n",
    "                res = min(res, s + f(i + 1, j + k))\n",
    "                k += 1 \n",
    "            return res \n",
    "        return f(0, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        n, m = len(robot), len(factory)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if j == m - 1:\n",
    "                if factory[j][1] < n - i:\n",
    "                    return inf\n",
    "                return sum(abs(x-factory[j][0]) for x in robot[i:])\n",
    "            \n",
    "            res = dfs(i, j+1)\n",
    "            s, k = 0, 1\n",
    "            while k <= factory[j][1] and i + k - 1 < n:\n",
    "                s += abs(robot[i+k-1] - factory[j][0])\n",
    "                res = min(res, s + dfs(i+k, j+1))\n",
    "                k += 1\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        factory.sort(key=lambda f: f[0])\n",
    "        robot.sort()\n",
    "        n, m = len(factory), len(robot)\n",
    "        @cache\n",
    "        def f(i: int, j: int) -> int:\n",
    "            if j == m: return 0\n",
    "            if i == n - 1:\n",
    "                \n",
    "\n",
    "                if m - j > factory[i][1]: return inf\n",
    "                return sum(abs(x - factory[i][0]) for x in robot[j:])\n",
    "            res = f(i + 1, j)\n",
    "            s, k = 0, 1\n",
    "            while k <= factory[i][1] and j + k - 1 < m:\n",
    "                s += abs(robot[j + k - 1] - factory[i][0])\n",
    "                res = min(res, s + f(i + 1, j + k))\n",
    "                k += 1\n",
    "            return res\n",
    "        return f(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        # 1. 递归： 邻项交换：对机器人和工厂按照位置大小重新排序，每个工厂修复的机器人就是连续的一段\n",
    "        factory.sort(key = lambda f: f[0])\n",
    "        robot.sort()\n",
    "        n, m = len(factory), len(robot)\n",
    "\n",
    "        @cache\n",
    "        def f(i:int, j:int)-> int: # f(i,j) 表示用第i个及其右侧的工厂，修理第j个及其右侧的机器人，移动的最小总距离\n",
    "            if j == m: return 0\n",
    "            if i == n - 1:\n",
    "                if m - j > factory[i][1]: return inf\n",
    "                return sum(abs(x - factory[i][0])for x in robot[j:])\n",
    "            res = f(i + 1, j)\n",
    "            s, k = 0, 1\n",
    "            while k <= factory[i][1] and j + k - 1 < m:\n",
    "                s += abs(robot[j + k - 1] - factory[i][0])\n",
    "                res = min(res, s + f(i + 1, j + k)) # \n",
    "                k += 1\n",
    "            return res\n",
    "        return f(0, 0)\n",
    "    \n",
    "        # 2. 递推\n",
    "        factory.sort(k = lambda f: f[0])\n",
    "        robot.sort()\n",
    "        m = len(robot)\n",
    "        f = [0] + [inf] * m\n",
    "        for pos, limit in factory:\n",
    "            for j in range(m, 0, -1):\n",
    "                cost = 0\n",
    "                for k in range(1, min(j, limit) + 1):\n",
    "                    cost += abs(robot[j - k] - pos)\n",
    "                    f[j] = min(f[j], f[j - k] + cost)\n",
    "        return f[m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\r\n",
    "        factory.sort(key=lambda f: f[0])\r\n",
    "        robot.sort()\r\n",
    "        n, m = len(factory), len(robot)\r\n",
    "        @cache\r\n",
    "        def f(i: int, j: int) -> int:\r\n",
    "            if j == m: return 0\r\n",
    "            if i == n - 1:\r\n",
    "                if m - j > factory[i][1]: return inf\r\n",
    "                return sum(abs(x - factory[i][0]) for x in robot[j:])\r\n",
    "            res = f(i + 1, j)\r\n",
    "            s, k = 0, 1\r\n",
    "            while k <= factory[i][1] and j + k - 1 < m:\r\n",
    "                s += abs(robot[j + k - 1] - factory[i][0])\r\n",
    "                res = min(res, s + f(i + 1, j + k))\r\n",
    "                k += 1\r\n",
    "            return res\r\n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\r\n",
    "        factory.sort(key=lambda f: f[0])\r\n",
    "        robot.sort()\r\n",
    "        n, m = len(factory), len(robot)\r\n",
    "        @cache\r\n",
    "        def f(i: int, j: int) -> int:\r\n",
    "            if j == m: return 0\r\n",
    "            if i == n - 1:\r\n",
    "                if m - j > factory[i][1]: return inf\r\n",
    "                return sum(abs(x - factory[i][0]) for x in robot[j:])\r\n",
    "            res = f(i + 1, j)\r\n",
    "            s, k = 0, 1\r\n",
    "            while k <= factory[i][1] and j + k - 1 < m:\r\n",
    "                s += abs(robot[j + k - 1] - factory[i][0])\r\n",
    "                res = min(res, s + f(i + 1, j + k))\r\n",
    "                k += 1\r\n",
    "            return res\r\n",
    "        return f(0, 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "\n",
    "        factory.sort(key=lambda f: f[0])\n",
    "\n",
    "        robot.sort()\n",
    "\n",
    "        n, m = len(factory), len(robot)\n",
    "\n",
    "        @cache\n",
    "\n",
    "        def f(i: int, j: int) -> int:\n",
    "\n",
    "            if j == m: return 0\n",
    "\n",
    "            if i == n - 1:\n",
    "\n",
    "                if m - j > factory[i][1]: return inf\n",
    "\n",
    "                return sum(abs(x - factory[i][0]) for x in robot[j:])\n",
    "\n",
    "            res = f(i + 1, j)\n",
    "\n",
    "            s, k = 0, 1\n",
    "\n",
    "            while k <= factory[i][1] and j + k - 1 < m:\n",
    "\n",
    "                s += abs(robot[j + k - 1] - factory[i][0])\n",
    "\n",
    "                res = min(res, s + f(i + 1, j + k))\n",
    "\n",
    "                k += 1\n",
    "\n",
    "            return res\n",
    "\n",
    "        return f(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        factory.sort(key=lambda f: f[0])\n",
    "        robot.sort()\n",
    "        n, m = len(factory), len(robot)\n",
    "        @cache\n",
    "        def f(i: int, j: int) -> int:\n",
    "            if j == m: return 0\n",
    "            if i == n - 1:\n",
    "                if m - j > factory[i][1]: return inf\n",
    "                return sum(abs(x - factory[i][0]) for x in robot[j:])\n",
    "            res = f(i + 1, j)\n",
    "            s, k = 0, 1\n",
    "            while k <= factory[i][1] and j + k - 1 < m:\n",
    "                s += abs(robot[j + k - 1] - factory[i][0])\n",
    "                res = min(res, s + f(i + 1, j + k))\n",
    "                k += 1\n",
    "            return res\n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        factory.sort(key=lambda f: f[0])\n",
    "        robot.sort()\n",
    "        n, m = len(factory), len(robot)\n",
    "        @cache\n",
    "        def f(i: int, j: int) -> int:\n",
    "            if j == m: return 0\n",
    "            if i == n - 1:\n",
    "                if m - j > factory[i][1]: return inf\n",
    "                return sum(abs(x - factory[i][0]) for x in robot[j:])\n",
    "            res = f(i + 1, j)\n",
    "            s, k = 0, 1\n",
    "            while k <= factory[i][1] and j + k - 1 < m:\n",
    "                s += abs(robot[j + k - 1] - factory[i][0])\n",
    "                res = min(res, s + f(i + 1, j + k))\n",
    "                k += 1\n",
    "            return res\n",
    "        return f(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        m = len(robot)\n",
    "        n = len(factory)\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == n:\n",
    "                if j == m:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            su = 0\n",
    "            ans = inf\n",
    "            # print(i, j)\n",
    "            for k in range(factory[i][1] + 1):\n",
    "                ans = min(ans, su + dfs(i + 1, j + k))\n",
    "                # print(\"k\", k, ans)\n",
    "                if j + k < m:\n",
    "                    su += abs(robot[j + k] - factory[i][0])\n",
    "                else:\n",
    "                    break\n",
    "            # print(i, j, ans)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 0)\n",
    "        \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        # 预处理所有距离\n",
    "        dis = [[abs(robot[i] - factory[j][0]) for j in range(n)] for i in range(m)]\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i <= 0: return 0\n",
    "            if j <= 0: return inf\n",
    "            # 返回tot, 代表前j个工厂装前i个机器人的最小距离\n",
    "            tot = dfs(i, j - 1)\n",
    "            # 第 j 个工厂最多可以装 min(factory[j][1], i)个机器人\n",
    "            # k 表示第 j 个工厂 装了多少个机器人\n",
    "            # disj 表示 第 j 个工厂 所有机器人的移动总距离\n",
    "            disj = 0\n",
    "            for k in range(1, min(factory[j - 1][1], i) + 1):\n",
    "                disj += dis[i - k][j - 1]\n",
    "                tot = min(tot, dfs(i - k, j - 1) + disj)\n",
    "            return tot\n",
    "        return dfs(m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        \n",
    "        # 预处理所有距离\n",
    "        dis = [[abs(robot[i] - factory[j][0]) for j in range(n)] for i in range(m)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i <= 0: return 0\n",
    "            if j <= 0: return float('inf')\n",
    "            # 返回tot, 代表前j个工厂装前i个机器人的最小距离\n",
    "            tot = dfs(i, j - 1)\n",
    "            \n",
    "            # 第 j 个工厂最多可以装 min(factory[j][1], i)个机器人\n",
    "            # k 表示第 j 个工厂 装了多少个机器人\n",
    "            # disj 表示 第 j 个工厂 所有机器人的移动总距离\n",
    "            disj = 0\n",
    "            for k in range(1, min(factory[j - 1][1], i) + 1):\n",
    "                disj += dis[i - k][j - 1]\n",
    "                tot = min(tot, dfs(i - k, j - 1) + disj)\n",
    "            return tot\n",
    "        \n",
    "        return dfs(m, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        m, n = len(robot), len(factory)\n",
    "        \n",
    "        # 预处理所有距离\n",
    "        dis = [[abs(robot[i] - factory[j][0]) for j in range(n)] for i in range(m)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i <= 0: return 0\n",
    "            if j <= 0: return float('inf')\n",
    "            # 返回tot, 代表前j个工厂装前i个机器人的最小距离\n",
    "            tot = dfs(i, j - 1)\n",
    "            \n",
    "            # 第 j 个工厂最多可以装 min(factory[j][1], i)个机器人\n",
    "            # k 表示第 j 个工厂 装了多少个机器人\n",
    "            # disj 表示 第 j 个工厂 所有机器人的移动总距离\n",
    "            disj = 0\n",
    "            for k in range(1, min(factory[j - 1][1], i) + 1):\n",
    "                disj += dis[i - k][j - 1]\n",
    "                tot = min(tot, dfs(i - k, j - 1) + disj)\n",
    "            return tot\n",
    "        \n",
    "        return dfs(m, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:\n",
    "        rl = len(robot)\n",
    "        fl = len(factory)\n",
    "        robot.sort()\n",
    "        factory.sort()\n",
    "        f = [[[10 ** 18] * (rl + 1) for i in range(rl + 1)] for _ in range(fl + 1)]\n",
    "        g = [[10 ** 18] * (rl + 1) for _ in range(fl + 1)]\n",
    "        \n",
    "        for i in range(fl + 1):\n",
    "            g[i][0] = 0\n",
    "        \n",
    "        cnt = 0\n",
    "        s = [0] * (fl + 1)\n",
    "        for i in range(fl):\n",
    "            s[i + 1] = s[i] + factory[i][1]\n",
    "        for i in range(1, fl + 1):\n",
    "            fp = factory[i - 1][0]\n",
    "            for j in range(1, min(s[i], rl) + 1):\n",
    "                g[i][j] = g[i - 1][j]\n",
    "                d = 0\n",
    "                for k in range(j, max(j - factory[i - 1][1], 0), -1):\n",
    "                    d += abs(fp - robot[k - 1])\n",
    "                    f[i][j][k] = min(f[i][j][k], g[i - 1][k - 1] + d)\n",
    "                    g[i][j] = min(g[i][j], f[i][j][k])\n",
    "                # print(i, j, g[i][j])\n",
    "        \n",
    "        ret = g[fl][rl]\n",
    "        # print(ret)\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
